// ultimate_stdc++.h
#ifndef ULTIMATE_STDCXX_H
#define ULTIMATE_STDCXX_H

// ==================== C++标准库头文件 ====================

// 输入输出流
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <istream>
#include <ostream>
#include <iostream>
#include <streambuf>

// 字符串处理
#include <string>
#include <string_view>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cstdio>
#include <cwchar>
#include <cwctype>

// 容器类
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <bitset>

// 算法
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <random>
#include <valarray>
#include <complex>
#include <ratio>
#include <cfenv>
#include <cmath>

// 内存管理
#include <memory>
#include <new>
#include <scoped_allocator>
#include <memory_resource>

// 实用工具
#include <utility>
#include <tuple>
#include <optional>
#include <variant>
#include <any>
#include <type_traits>
#include <typeinfo>
#include <typeindex>
#include <chrono>
#include <ctime>

// 异常处理
#include <exception>
#include <stdexcept>
#include <cassert>
#include <system_error>

// 多线程
#include <thread>
#include <mutex>
#include <shared_mutex>
#include <future>
#include <condition_variable>
#include <atomic>

// 文件系统
#include <filesystem>

// 正则表达式
#include <regex>

// 本地化
#include <locale>
#include <clocale>
#include <codecvt>

// 其他
#include <limits>
#include <cfloat>
#include <cstddef>
#include <cstdint>
#include <cinttypes>
#include <cstdarg>
#include <csignal>
#include <csetjmp>
#include <cuchar>

// ==================== C标准库头文件 ====================

// 数学函数
#include <cmath>
#include <cstdlib>
#include <complex.h>
#include <tgmath.h>
#include <fenv.h>

// 字符处理
#include <cctype>
#include <cwctype>
#include <cwchar>

// 字符串处理
#include <cstring>
#include <cuchar>
#include <cstdlib>

// 输入输出
#include <cstdio>
#include <cwchar>

// 错误处理
#include <cerrno>
#include <cassert>

// 内存管理
#include <cstdlib>
#include <cstring>

// 时间日期
#include <ctime>
#include <chrono>

// 信号处理
#include <csignal>
#include <csetjmp>

// 常量定义
#include <climits>
#include <cfloat>
#include <climits>
#include <cstdint>
#include <cinttypes>

// 其他C标准库
#include <cstdarg>
#include <cstdbool>
#include <cstddef>
#include <cstdint>
#include <cinttypes>
#include <ciso646>
#include <cuchar>
#include <cwchar>
#include <cwctype>

// ==================== 系统特定头文件 ====================

#ifdef _WIN32
    #include <windows.h>
    #include <winsock2.h>
    #include <ws2tcpip.h>
    #include <conio.h>
    #include <direct.h>
    #include <process.h>
    #include <tchar.h>
    #include <comdef.h>
#elif defined(__linux__)
    #include <unistd.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <sys/time.h>
    #include <sys/socket.h>
    #include <sys/ioctl.h>
    #include <sys/mman.h>
    #include <sys/wait.h>
    #include <netinet/in.h>
    #include <netdb.h>
    #include <arpa/inet.h>
    #include <fcntl.h>
    #include <dirent.h>
    #include <pthread.h>
    #include <dlfcn.h>
    #include <termios.h>
    #include <grp.h>
    #include <pwd.h>
    #include <shadow.h>
    #include <utmpx.h>
#endif

// ==================== 编译器特定扩展 ====================

#ifdef __GNUC__
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/rope>
    #include <ext/algorithm>
    #include <ext/numeric>
    #include <ext/functional>
    #include <ext/memory>
    #include <ext/iterator>
    
    // GCC优化指令
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,fma")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#endif

#ifdef _MSC_VER
    #pragma comment(lib, "ws2_32.lib")
    #pragma comment(lib, "user32.lib")
    #pragma comment(lib, "kernel32.lib")
    #pragma comment(lib, "gdi32.lib")
    #pragma optimize("gt", on)
#endif

// ==================== 常用命名空间 ====================

using namespace std;

// GCC扩展命名空间
#ifdef __GNUC__
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#endif

// ==================== 类型定义 ====================

// 基础类型
typedef signed char        s8;
typedef unsigned char      u8;
typedef short              s16;
typedef unsigned short     u16;
typedef int                s32;
typedef unsigned int       u32;
typedef long long          s64;
typedef unsigned long long u64;
typedef float              f32;
typedef double             f64;
typedef long double        f128;

// 标准类型别名
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vld = vector<ld>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvb = vector<vb>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;

// 复杂类型
using cpx = complex<double>;

// ==================== 常量定义 ====================

const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const int MOD998 = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const double GOLDEN_RATIO = 1.6180339887498948482;

// 方向数组
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};

// ==================== 宏定义 ====================

// 循环宏
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define repn(i, n) rep(i, 0, n)
#define repdn(i, n) repd(i, (n)-1, 0)
#define foreach(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)
#define foreachr(it, x) for (auto it = (x).rbegin(); it != (x).rend(); ++it)

// 容器操作
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ef emplace_front
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define empty(x) (x).empty()
#define clear(x) (x).clear()
#define resize(x, n) (x).resize(n)
#define reserve(x, n) (x).reserve(n)

// 数学宏
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max4(a, b, c, d) max(max(a, b), max(c, d))

// 位操作
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) |= (1LL << (i)))
#define clear_bit(x, i) ((x) &= ~(1LL << (i)))
#define toggle_bit(x, i) ((x) ^= (1LL << (i)))
#define low_bit(x) ((x) & -(x))
#define high_bit(x) (1LL << (63 - __builtin_clzll(x)))

// 调试宏
#ifdef DEBUG
    #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", _debug(__VA_ARGS__)
    #define dbg_var(x) cerr << #x << " = " << x << endl
    #define dbg_vec(v) cerr << #v << " = "; _debug_vec(v)
    #define dbg_mat(m) cerr << #m << " =\n"; _debug_mat(m)
    #define dbg_time() cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl
#else
    #define dbg(...) ((void)0)
    #define dbg_var(x) ((void)0)
    #define dbg_vec(v) ((void)0)
    #define dbg_mat(m) ((void)0)
    #define dbg_time() ((void)0)
#endif

// 断言宏
#define ASSERT(cond, msg) \
    do { \
        if (!(cond)) { \
            cerr << "Assertion failed: " << (msg) << " at " << __FILE__ << ":" << __LINE__ << endl; \
            abort(); \
        } \
    } while (0)

// ==================== 调试函数 ====================

void _debug() { cerr << endl; }
template<typename T, typename... Args>
void _debug(T first, Args... args) {
    cerr << " " << first;
    _debug(args...);
}

template<typename T>
void _debug_vec(const vector<T>& v) {
    cerr << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) cerr << ", ";
        cerr << v[i];
    }
    cerr << "]" << endl;
}

template<typename T>
void _debug_mat(const vector<vector<T>>& m) {
    for (const auto& row : m) {
        for (const auto& x : row) {
            cerr << x << " ";
        }
        cerr << endl;
    }
}

// ==================== 数学函数 ====================

template<typename T>
constexpr T gcd(T a, T b) {
    while (b) {
        T t = b;
        b = a % b;
        a = t;
    }
    return a;
}

template<typename T>
constexpr T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

template<typename T>
constexpr T mod_pow(T a, T b, T mod = MOD) {
    T res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

template<typename T>
constexpr T mod_inv(T a, T mod = MOD) {
    return mod_pow(a, mod - 2, mod);
}

// ==================== 高级数据结构 ====================

// 有序集合 (GCC扩展)
#ifdef __GNUC__
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename K, typename V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

// 哈希表增强
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    
    template<typename T, typename U>
    size_t operator()(const pair<T, U>& p) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(p.first + FIXED_RANDOM) ^ (splitmix64(p.second + FIXED_RANDOM) >> 1);
    }
};

template<typename K, typename V>
using hash_map = unordered_map<K, V, custom_hash>;

template<typename T>
using hash_set = unordered_set<T, custom_hash>;

// ==================== 随机数生成 ====================

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
T rand_range(T a, T b) {
    return uniform_int_distribution<T>(a, b)(rng);
}

template<typename T>
T rand_real(T a, T b) {
    return uniform_real_distribution<T>(a, b)(rng);
}

// ==================== 输入输出优化 ====================

class FastIO {
private:
    static const int BUFSIZE = 1 << 20;
    char inbuf[BUFSIZE], outbuf[BUFSIZE];
    int inpos, outpos, len;
    FILE *in, *out;
    
    inline char getChar() {
        if (inpos == len) {
            len = fread(inbuf, 1, BUFSIZE, in);
            inpos = 0;
            if (len == 0) return EOF;
        }
        return inbuf[inpos++];
    }

public:
    FastIO(FILE *_in = stdin, FILE *_out = stdout) : inpos(0), outpos(0), len(0), in(_in), out(_out) {}
    
    ~FastIO() {
        flush();
    }
    
    template<typename T>
    inline void read(T &x) {
        x = 0;
        char c;
        bool neg = false;
        
        while ((c = getChar()) <= ' ');
        if (c == '-') {
            neg = true;
            c = getChar();
        }
        
        do {
            x = x * 10 + (c - '0');
        } while ((c = getChar()) >= '0');
        
        if (neg) x = -x;
    }
    
    inline void read(char &c) {
        while ((c = getChar()) <= ' ');
    }
    
    inline void read(string &s) {
        s.clear();
        char c;
        while ((c = getChar()) <= ' ');
        do {
            s += c;
        } while ((c = getChar()) > ' ');
    }
    
    inline void write(char c) {
        if (outpos == BUFSIZE) flush();
        outbuf[outpos++] = c;
    }
    
    template<typename T>
    inline void write(T x) {
        if (x < 0) {
            write('-');
            x = -x;
        }
        
        char buf[20];
        int pos = 0;
        do {
            buf[pos++] = '0' + x % 10;
            x /= 10;
        } while (x > 0);
        
        while (pos > 0) {
            write(buf[--pos]);
        }
    }
    
    inline void write(const string &s) {
        for (char c : s) write(c);
    }
    
    inline void flush() {
        if (outpos > 0) {
            fwrite(outbuf, 1, outpos, out);
            outpos = 0;
        }
    }
};

// ==================== 性能计时器 ====================

class Timer {
private:
    chrono::high_resolution_clock::time_point start_time;
    string name;
    
public:
    Timer(const string& timer_name = "") : name(timer_name) {
        start_time = chrono::high_resolution_clock::now();
    }
    
    ~Timer() {
        auto end_time = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
        if (!name.empty()) {
            cerr << name << " took " << duration.count() << " ms" << endl;
        }
    }
    
    double elapsed() const {
        auto end_time = chrono::high_resolution_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
    }
};

// ==================== 内存检测 ====================

#ifdef DEBUG
class MemoryMonitor {
private:
    static const int MAX_ALLOCS = 100000;
    struct Allocation {
        void* ptr;
        size_t size;
        const char* file;
        int line;
    };
    static vector<Allocation> allocations;
    
public:
    static void* track_alloc(size_t size, const char* file, int line) {
        void* ptr = malloc(size);
        allocations.push_back({ptr, size, file, line});
        return ptr;
    }
    
    static void track_free(void* ptr) {
        auto it = find_if(all(allocations), [ptr](const Allocation& a) {
            return a.ptr == ptr;
        });
        if (it != allocations.end()) {
            free(ptr);
            allocations.erase(it);
        }
    }
    
    static void report() {
        cerr << "Memory allocations: " << allocations.size() << endl;
        for (const auto& alloc : allocations) {
            cerr << "Leak: " << alloc.size << " bytes at " << alloc.file << ":" << alloc.line << endl;
        }
    }
};

vector<MemoryMonitor::Allocation> MemoryMonitor::allocations;

void* operator new(size_t size, const char* file, int line) {
    return MemoryMonitor::track_alloc(size, file, line);
}

void* operator new[](size_t size, const char* file, int line) {
    return MemoryMonitor::track_alloc(size, file, line);
}

void operator delete(void* ptr) noexcept {
    MemoryMonitor::track_free(ptr);
}

void operator delete[](void* ptr) noexcept {
    MemoryMonitor::track_free(ptr);
}

#define new new(__FILE__, __LINE__)
#endif

// ==================== 全局初始化 ====================

struct Initializer {
    Initializer() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cerr.tie(nullptr);
        
        // 设置浮点数输出精度
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
        
        // 随机数种子
        srand(time(nullptr));
        
#ifdef DEBUG
        atexit(MemoryMonitor::report);
#endif
    }
} initializer;

#endif // ULTIMATE_STDCXX_H